﻿#include "MST.h"
#include <vector>
#include <map>
#include <iostream>
#include <set>
#include <limits>
#include <list>
#include <stack>
#include <math.h>


using namespace std;

Point RandomGraph::generateRandomPoint(Point center, int sigma) {
	double s=0; 
	double x, y;
	while (s==0 || s>1) {
		x=(2.0*rand()-RAND_MAX)/RAND_MAX;
		y=(2.0*rand()-RAND_MAX)/RAND_MAX;
		s = x*x + y*y;
	}
	
	x=x*sqrt(-2.0*(log(s)/s))*sigma+center.x;
    y=y*sqrt(-2.0*(log(s)/s))*sigma+center.y;
	Point point=Point(x, y);
	//cout<<"New point is: "<<point.x<<" "<<point.y<<endl;
	return point;
}

/*RandomGraph::RandomGraph(Point center, int sigma1, int sigma2, int num1, int num2) {
	for (int i=0; i<num1; i++) {
	   Point point=generateRandomPoint(center, sigma1);
	   verteces.push_back(point);
	   for (int j=0; j<num2; j++) {
		   Point point1=generateRandomPoint(point, sigma2);
		   verteces.push_back(point1);
	   }
   }      
}*/

int RandomGraph::getDistance(int v1, int v2) {
	double dx = verteces[v1].x - verteces[v2].x;
    double dy = verteces[v1].y - verteces[v2].y;
    return sqrt(dx*dx + dy*dy);
}

Point RandomGraph::getVertex(int v) {
	if (v<0 || v>verteces.size()) {
		throw exception("Wrong index");
	}
	return verteces[v];
}

void MST::getPrim(vector<pair<int, int>>& edges, vector<vector<int>>& vert) {
	vector<double> distance; // массив расстояний до дерева
	vector<int> parent; // массив предков
	//vector <bool> used;
	PriorityQueue<double, int> queue;
	vector <bool> unused;

	int size=rg.size();

	unused.assign(size, true);
	distance.assign(size, numeric_limits<double>::infinity());
	parent.assign(size, 0);
	distance[0]=0;

	queue.push(0, 0);
	parent[0]=-1;

	vert.push_back(vector<int>());
	for (int i=1; i<size; i++) {
        queue.push(numeric_limits<double>::infinity(), i);
		vert.push_back(vector<int>());
	} 
	cout<<"Size of vert: "<<vert.size()<<endl;
	while (!queue.empty()) {

		int v=queue.pop();
		//cout<<v<<endl;
		unused[v]=false;
		if ( parent[v] != -1 ) {
			edges.push_back( pair<int, int>( v, parent[v] ) );
			vert[v].push_back(parent[v]);
			vert[parent[v]].push_back(v);
			//cout<<"lala"<<endl;
		}

		for (int i = 0; i < size; i++) {  // пересчитываем расстояние от вершин до дерева
			double dist=rg.getDistance(v,i);
			if ((unused[i]) && (dist < distance[i]) && ( v != i )) {
				distance[i]=dist;
				queue.changeKey(dist, i);
				parent[i] = v;
			}
		}
	}
}


void MST::eulerianPath(vector<vector<int>>& vert, vector<int>& way) {
     //Ищем Эйлеров цикл обходом остовного дерева по всем ребрам, затем повторяющиеся вершины удалим
     stack<int> stackS;
     int strt = 0;
     set<pair<int, int>> closed;

     stackS.push(strt);
     while (!stackS.empty()) {
           int u = stackS.top();
           bool allClosed = true;
           for (int i=0; i<vert[u].size(); i++) {
			   int w=vert[u][i];
               pair<int, int> pr = make_pair(u,w);
               if (closed.find(pr) == closed.end()) {
                   allClosed = false;
                   closed.insert(pr);
                   stackS.push(w);
               }
           }
           if (allClosed) {
               way.push_back(u);
               stackS.pop();
           }
     }
}

void MST::getKr(vector<pair<int, int>>& res_edges) {
	vector < pair<double, pair<int,int>> > edges; // ребра графа
	int vSize = rg.size();
	vector <int> treeId(vSize); // 
	
	for (int i=0; i<vSize; ++i ) {
		treeId[i] = i;
	}

        
     for (int i=0 ; i<vSize - 1; i++ ) {
		 for (int j=i+1; j<vSize; j++ ) {
			 edges.push_back( pair<double, pair<int,int>>( rg.getDistance(i,j), pair<int,int>(i, j)) );
		 }
	 }
	 
	 sort( edges.begin(), edges.end() );
	 for ( int i = 0; i < edges.size(); ++i ) {
		 int v1 = edges[i].second.first;
		 int v2 = edges[i].second.second;
		 int distance = edges[i].first;

		 if ( treeId[v1] != treeId[v2] ) {
			 res_edges.push_back( pair<int, int>(v1, v2) );
			 int oldId = treeId[v2];
			 int newId = treeId[v1];
			 for ( int j = 0; j < vSize; ++j ) {
				 if ( treeId[j] == oldId) {
					 treeId[j] = newId;
				 }
			 }
		 }
	 }
}